<?php
// https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/

// 我们用一个大根堆实时维护数组的前 k 小值。首先将前 kk 个数插入大根堆中，随后从第 k+1个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];

        if (k == 0) { // 排除 0 的情况
            return vec;
        }

        // 堆比较
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });

        // 初始化堆
        for (int i = 0; i < k; ++i) {
             queue.offer(arr[i]);
        }

        // k开始和堆顶比较，小于堆顶 =》 交换
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        // 取出堆的元素
        for (int i = 0; i < k; ++i) {
             vec[i] = queue.poll();
        }

        return vec;
    }
}

// 时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。

// 空间复杂度：O(k)，因为大根堆里最多 k 个数。